Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordconsists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
Average Rating: 4.89 (153 votes)
Solution
Approach 1: Backtracking
Intuition
This problem is yet another 2D grid traversal problem, which is similar with another problem called 489. Robot Room Cleaner.
Many people in the discussion forum claimed that the solution is of DFS (Depth-First Search). Although it is true that we would explore the 2D grid with the DFS strategy for this problem, it does not capture the entire nature of the solution.
We argue that a more accurate term to summarize the solution would be backtracking, which is a methodology where we mark the current path of exploration, if the path does not lead to a solution, we then revert the change (i.e. backtracking) and try another path.
As the general idea for the solution, we would walk around the 2D grid, at each step we mark our choice before jumping into the next step. And at the end of each step, we would also revert our marking, so that we could have a clean slate to try another direction. In addition, the exploration is done via the DFS strategy, where we go as further as possible before we try the next direction.
Algorithm
There is a certain code pattern for all the algorithms of backtracking. For example, one can find one template in our Explore card of Recursion II.
The skeleton of the algorithm is a loop that iterates through each cell in the grid. For each cell, we invoke the backtracking function (i.e. backtrack()) to check if we would obtain a solution, starting from this very cell.
For the backtracking function backtrack(row, col, suffix), as a DFS algorithm, it is often implemented as a recursive function. The function can be broke down into the following four steps:
-
Step 1). At the beginning, first we check if we reach the bottom case of the recursion, where the word to be matched is empty, i.e. we have already found the match for each prefix of the word.
-
Step 2). We then check if the current state is invalid, either the position of the cell is out of the boundary of the board or the letter in the current cell does not match with the first letter of the word.
-
Step 3). If the current step is valid, we then start the exploration of backtracking with the strategy of DFS. First, we mark the current cell as visited, e.g. any non-alphabetic letter will do. Then we iterate through the four possible directions, namely up, right, down and left. The order of the directions can be altered, to one's preference.
-
Step 4). At the end of the exploration, we revert the cell back to its original state. Finally we return the result of the exploration.
We demonstrate how it works with an example in the following animation.
Notes
There are a few choices that we made for our backtracking algorithm, here we elaborate some thoughts that are behind those choices.
Instead of returning directly once we find a match, we simply break out of the loop and do the cleanup before returning.
Here is what the alternative solution might look like.
As once notices, we simply return True if the result of recursive call to backtrack() is positive. Though this minor modification would have no impact on the time or space complexity, it would however leave with some "side-effect", i.e. the matched letters in the original board would be altered to #.
Instead of doing the boundary checks before the recursive call on the
backtrack()function, we do it within the function.
This is an important choice though. Doing the boundary check within the function would allow us to reach the bottom case, for the test case where the board contains only a single cell, since either of neighbor indices would not be valid.
Complexity Analysis
-
Time Complexity: O(N⋅3L) where N is the number of cells in the board and L is the length of the word to be matched.
-
For the backtracking function, initially we could have at most 4 directions to explore, but further the choices are reduced into 3 (since we won't go back to where we come from). As a result, the execution trace after the first step could be visualized as a 3-ary tree, each of the branches represent a potential exploration in the corresponding direction. Therefore, in the worst case, the total number of invocation would be the number of nodes in a full 3-nary tree, which is about 3L.
-
We iterate through the board for backtracking, i.e. there could be N times invocation for the backtracking function in the worst case.
-
As a result, overall the time complexity of the algorithm would be O(N⋅3L).
-
-
Space Complexity: O(L) where L is the length of the word to be matched.
- The main consumption of the memory lies in the recursion call of the backtracking function. The maximum length of the call stack would be the length of the word. Therefore, the space complexity of the algorithm is O(L).
- The main consumption of the memory lies in the recursion call of the backtracking function. The maximum length of the call stack would be the length of the word. Therefore, the space complexity of the algorithm is O(L).
February 26, 2020 11:35 PM
The quality of these articles are getting better and better. Very well written!
March 16, 2020 12:43 PM
I think the overall time complexity is closer to O(N*3^min(L, N)).
Each cell has only 3 directions to be potentially explored because one direction has been already visited by its parent.
So, the worst case can be expressed by N * 4 * 3^min(L - 1, N - 1) (4 means the beginning point) and by big O,
O(N * 3^min(L, N))
March 13, 2020 7:04 AM
One thing that got me is the early return ret. I got a TLE due to not have the ret block.
Something like this doesn't work, since we'll still recurse all those different options, even when we have already found a valid path.
boolean left = dfs(board, word, idx + 1, i + 1, j);
boolean top = dfs(board, word, idx + 1, i - 1, j);
boolean right = dfs(board, word, idx + 1, i, j + 1);
boolean bottom = dfs(board, word, idx + 1, i, j - 1);
return (left || top || right || bottom);
Great work on the edge cases for this test.
February 4, 2020 8:38 AM
I hope this is more understandable for some people since I am a beginner.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(word, i, j, match_idx, directions, board, visited):
if match_idx == len(word) - 1:
return True
# try all four directions
for dx, dy in directions:
x = i + dx
y = j + dy
# if within the board, never visited, and matches the current char, keep matching the next char
if 0 <= x < len(board) and 0 <= y < len(board[0]) and visited[x][y] == False and board[x][y] == word[match_idx + 1]:
visited[x][y] = True
if dfs(word, x, y, match_idx + 1, directions, board, visited):
return True
visited[x][y] = False
m = len(board)
n = len(board[0])
directions = ((1, 0), (0, 1), (-1, 0), (0, -1))
visited = [[False for _ in range(n)] for _ in range(m)]
# find the starting char
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
visited[i][j] = True
match_idx = 0
if dfs(word, i, j, match_idx, directions, board, visited):
return True
visited[i][j] = False
return False
July 1, 2020 8:53 PM
DFS solution would have been more direct!
December 19, 2020 11:09 AM
It's surprising they would suggest you modify the original grid when you could also maintain a visited hashset.
February 4, 2020 8:37 AM
Time complexity is not thorough. If L is super long, 4^L will be bounded by N. So better expressed as
O(N*(4^L+N)), plus means whichever larger.
December 17, 2020 2:10 PM
Is this testcase correct? : [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"
February 3, 2021 5:05 AM
I think test cases are weak. In the constraints it's mentioned that 1 <= L <= 10^3. How come O(N*(3^1000)) is running within 1sec? Consider a test case in which the number of rows = number of columns = 30 and all the cells in the board are A except the cell(n-1, m-1) which is B. Word to match is AA.....A (1000 As)
November 17, 2020 6:08 AM
My solution got accepted, but it fails with my private testcase:
[["A","B","C","D"],["E","F","G","H"],["I","A","K","L"]]
"AIEFGKLHDCBA"
xxxxxxxxxxclass Solution {public: bool exist(vector<vector<char>>& board, string word) { for(int i=0;i<board.size();i++) { for(int j=0;j<board[i].size();j++) { if(board[i][j] == word[0]) { if(dfs(board, i, j, word, 0)) return true; } } } return false; } bool dfs(vector<vector<char>>& board, int i, int j, string& word, int idx) { if(i<0 || j<0 || i==board.size() || j==board[0].size() || word[idx] != board[i][j]) return false; if(idx == word.length()-1) return true; char c = board[i][j]; board[i][j] = '$'; bool found = dfs(board, i-1, j, word, idx+1) || dfs(board, i+1, j, word, idx+1) || dfs(board, i, j-1, word, idx+1) || dfs(board, i, j+1, word, idx+1); board[i][j] = c; return found; }};